{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #24 Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: judgePoint24"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #24 点游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为4的整数数组&nbsp;<code>cards</code>&nbsp;。你有 <code>4</code> 张卡片，每张卡片上都包含一个范围在 <code>[1,9]</code> 的数字。您应该使用运算符&nbsp;<code>['+', '-', '*', '/']</code>&nbsp;和括号&nbsp;<code>'('</code>&nbsp;和&nbsp;<code>')'</code>&nbsp;将这些卡片上的数字排列成数学表达式，以获得值24。</p>\n",
    "\n",
    "<p>你须遵守以下规则:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>除法运算符 <code>'/'</code> 表示实数除法，而不是整数除法。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>例如，&nbsp;<code>4 /(1 - 2 / 3)= 4 /(1 / 3)= 12</code>&nbsp;。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>每个运算都在两个数字之间。特别是，不能使用 <code>“-”</code> 作为一元运算符。\n",
    "\t<ul>\n",
    "\t\t<li>例如，如果 <code>cards =[1,1,1,1]</code> ，则表达式 <code>“-1 -1 -1 -1”</code> 是 <strong>不允许</strong> 的。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>你不能把数字串在一起\n",
    "\t<ul>\n",
    "\t\t<li>例如，如果 <code>cards =[1,2,1,2]</code> ，则表达式 <code>“12 + 12”</code> 无效。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果可以得到这样的表达式，其计算结果为 <code>24</code> ，则返回 <code>true </code>，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> cards = [4, 1, 8, 7]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> (8-4) * (7-1) = 24\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> cards = [1, 2, 1, 2]\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>cards.length == 4</code></li>\n",
    "\t<li><code>1 &lt;= cards[i] &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [24-game](https://leetcode.cn/problems/24-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [24-game](https://leetcode.cn/problems/24-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,8,7]', '[1,2,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0) # 摸一张 (queue 操作)\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0) # 再摸一张 (queue 操作)\n",
    "                for value in [a + b, a - b, a * b, b and a / b, b - a, a and b / a]: # 算一下\n",
    "                    cards.append(value) # 记下来 (stack 操作)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop() # (stack 操作)\n",
    "                cards.append(b) # (queue 操作)\n",
    "            cards.append(a) # (queue 操作)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "\n",
    "        bad = '떢븻각걎냇갅갸꺚뵟숣욄뵴뵞뤼갈갌뤔떌옊메늄숭캸긶꺛옖갍뇐쩢곴듇걯궄옕왹눞솴걃끗긬땉궿가쌀낐걄숤'\n",
    "        bad += '뺴늘걘꽸숢걂갋갃쫐꼔솾쩡쇔솿끛뤜간븺쩬웨딴옠뤛갂뵪덠놤빐옋귒늂갰갖놥궾갆옌뼘묰거갎긷낤겼'\n",
    "        return chr(int(''.join(map(str, sorted(cards)))) + 42921) not in bad"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        bad = \"对撒剘劥圞剜劏哱掶桺泛揋掵従剟剣彫寣污悫壛梄甏咍哲汭剤堧点卋嬞\" \\\n",
    "              \"勆叛汬泐塵栋劚嚮咃宠吖剗楗囧力桻攋壯劯嗏桹劙剢剚焧啫栕炸栫栖嚲\" \\\n",
    "              \"彳剛撑烃洿宋汷彲剙揁妷埻撧汢吩壙劇剭埼吕剝汣敯憇勇剥咎囻匓\"\n",
    "        return chr(int(''.join(map(str, sorted(cards)))) + 19968) not in bad"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        bad = \"对撒剘劥圞剜劏哱掶桺泛揋掵従剟剣彫寣污悫壛梄甏咍哲汭剤堧点卋嬞\" \\\n",
    "              \"勆叛汬泐塵栋劚嚮咃宠吖剗楗囧力桻攋壯劯嗏桹劙剢剚焧啫栕炸栫栖嚲\" \\\n",
    "              \"彳剛撑烃洿宋汷彲剙揁妷埻撧汢吩壙劇剭埼吕剝汣敯憇勇剥咎囻匓\"\n",
    "        return chr(int(''.join(map(str, sorted(cards)))) + 19968) not in bad"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        que = [cards]\n",
    "\n",
    "        for _ in range(3): # 每次随机选两个数进行四则运算，合并成一个数；4个数到1个数需要运算3次\n",
    "            n = len(que)\n",
    "            for _ in range(n):\n",
    "                currentCards = que.pop(0) # 当前的数组\n",
    "\n",
    "                for i in range(len(currentCards)):\n",
    "                    for j in range(len(currentCards)):\n",
    "                        if i != j:\n",
    "                            temp = [x for x in currentCards]\n",
    "                            a = currentCards[i]\n",
    "                            b = currentCards[j]\n",
    "                            temp.remove(a)\n",
    "                            temp.remove(b)\n",
    "\n",
    "                            que.append(temp + [a + b])\n",
    "                            que.append(temp + [a - b])\n",
    "                            que.append(temp + [a * b])\n",
    "                            if b != 0:\n",
    "                                que.append(temp + [a / b])\n",
    "        \n",
    "        for x in que:\n",
    "            if abs(x[0] - 24) < 10 ** -6:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"解题思路：\n",
    "    一、全排列枚举计算\n",
    "    1.枚举所有数字的组合，2^4种\n",
    "    2.组合之间两两进行计算,这里对(((a*b)*c)*d)和(a*b)*(c*d)分别进行了处理，他们好像是不包含的\n",
    "    3.结果出现24则返回True，一直没有则false\n",
    "    因为数字组合数固定，计算符组合也固定，则时间复杂度为常数O(1)\n",
    "\n",
    "    注：添加了一个计算缓存，避免重复计算\n",
    "    \"\"\"\n",
    "\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        arranges = []\n",
    "        self._arrange(nums, arranges, [])\n",
    "        for arrange in arranges:\n",
    "            if self._canGet24(arrange):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def _arrange(self, nums, arranges, path):\n",
    "        \"\"\"数字全排列\"\"\"\n",
    "        if len(path) == 4:\n",
    "            arranges.append(path.copy())\n",
    "            return\n",
    "\n",
    "        for i in range(0, len(nums)):\n",
    "            path.append(nums[i])\n",
    "            self._arrange(nums[:i] + nums[i+1:], arranges, path)\n",
    "            path.pop()\n",
    "\n",
    "    def _canGet24(self, arrange):\n",
    "        \"\"\"两两直接计算\"\"\"\n",
    "        for val1 in self._compute(arrange[0], arrange[1]):\n",
    "            for val2 in self._compute(val1, arrange[2]):\n",
    "                for val3 in self._compute(val2, arrange[3]):\n",
    "                    if abs(val3-24.0) < 1e-5:\n",
    "                        return True\n",
    "        for val1 in self._compute(arrange[0], arrange[1]):\n",
    "            for val2 in self._compute(arrange[2], arrange[3]):\n",
    "                for val3 in self._compute(val1, val2):\n",
    "                    if abs(val3-24.0) < 1e-5:\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def _compute(self, lvals, rvals):\n",
    "        \"\"\"返回两数直接可能的计算结果\"\"\"\n",
    "        res = [lvals + rvals, rvals + lvals, lvals - rvals, rvals - lvals]\n",
    "        if lvals != 0 and rvals != 0:\n",
    "            res.append(lvals * rvals)\n",
    "            res.append(lvals / rvals)\n",
    "            res.append(rvals / lvals)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0],24)\n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0)  # 拿出第一张\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0) # 再拿出一张\n",
    "                for value in [a+b,a-b,a*b, b and a/b]:\n",
    "                     #将其中两张牌分别用多种分发合并为一张牌，并判断\n",
    "                    cards.append(value)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        return self.compute_dfs(cards)\n",
    "\n",
    "    def compute_dfs(self, cards):\n",
    "        if len(cards) == 1:\n",
    "            if abs(cards[0] - 24) < 1e-2:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        for nums in itertools.permutations(cards):\n",
    "            # get 2 elem from nums\n",
    "            nums = list(nums)\n",
    "            for k, p in self.get_index(len(nums)):\n",
    "                for v in self.get_all_posible_value(nums[k], nums[p]):\n",
    "                    tmp = [v] + nums[:k] + nums[p+1:]\n",
    "                    ret = self.compute_dfs(tmp)\n",
    "                    if ret:\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def get_index(self, n):\n",
    "        for k in range(n-1):\n",
    "            yield k, k+1\n",
    "\n",
    "    def get_all_posible_value(self, a, b):\n",
    "        if b == 0:\n",
    "            return [a+b, a-b, a*b]\n",
    "        else:\n",
    "            return [a+b, a-b, a*b, a/b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        if not nums: return False\n",
    "        def helper(nums):\n",
    "            if len(nums) == 1: return abs(nums[0]-24) < 1e-6\n",
    "            for i in range(len(nums)):\n",
    "                for j in range(len(nums)):\n",
    "                    if i != j:\n",
    "                        newnums = [nums[k] for k in range(len(nums)) if i != k != j]\n",
    "                        if helper(newnums + [nums[i]+nums[j]]): return True\n",
    "                        if helper(newnums + [nums[i]-nums[j]]): return True\n",
    "                        if helper(newnums + [nums[i]*nums[j]]): return True\n",
    "                        if nums[j] != 0 and helper(newnums + [nums[i]/nums[j]]): return True\n",
    "            return False\n",
    "        return helper(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def dfs(cards):\n",
    "            if len(cards) == 1:\n",
    "                return (abs(cards[0]-24) < 1e-6)\n",
    "            for i in range(len(cards)-1):\n",
    "                for j in range(i+1,len(cards)):\n",
    "                    res = []\n",
    "                    for l in range(len(cards)):\n",
    "                        if l != i and l != j:\n",
    "                            res.append(cards[l])\n",
    "                    if dfs(res+[cards[i]+cards[j]]):\n",
    "                        return True\n",
    "                    elif dfs(res+[cards[i]-cards[j]]):\n",
    "                        return True\n",
    "                    elif dfs(res+[cards[j]-cards[i]]):\n",
    "                        return True\n",
    "                    elif dfs(res+[cards[i]*cards[j]]):\n",
    "                        return True\n",
    "                    elif cards[j]!= 0 and dfs(res+[cards[i]/cards[j]]):\n",
    "                        return True\n",
    "                    elif cards[i] != 0 and dfs(res+[cards[j]/cards[i]]):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(cards)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0) # 摸一张 (queue 操作)\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0) # 再摸一张 (queue 操作)\n",
    "                for value in [a + b, a - b, a * b, b and a / b]: # 算一下\n",
    "                    cards.append(value) # 记下来 (stack 操作)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop() # (stack 操作)\n",
    "                cards.append(b) # (queue 操作)\n",
    "            cards.append(a) # (queue 操作)\n",
    "        return False\n",
    "\n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def calculate(num1,num2):\n",
    "            return set([num1*num2,num1/num2 if num2 != 0 else 0,num2/num1 if num1 != 0 else 0,num1-num2,num2-num1,num1+num2])\n",
    "        #cards = [8,1,6,6]\n",
    "        for i in range(1,4):\n",
    "            rest = [j for j in range(1,4) if j != i]\n",
    "            set1 = calculate(cards[0], cards[i])\n",
    "            set2 = calculate(cards[rest[0]], cards[rest[1]])\n",
    "            for num1 in set1:\n",
    "                for num2 in set2:\n",
    "                    for num in calculate(num1, num2):\n",
    "                        if (num - 24)**2 <= 0.001:\n",
    "                            #print(i)\n",
    "                            return True\n",
    "        for i in range(4):\n",
    "            for j in range(4):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                rest = [k for k in range(4) if (k != i and k != j)]\n",
    "                for num2 in calculate(cards[rest[0]], cards[rest[1]]):\n",
    "                    for num1 in calculate(cards[j], num2):\n",
    "                        for num in calculate(cards[i], num1):\n",
    "                            if (num - 24)**2 <= 0.001:\n",
    "                                # print(cards[i],num1)\n",
    "                                # print(calculate(cards[i], num1))\n",
    "                                # print(cards[j], num2)\n",
    "                                # print(calculate(cards[j], num2))\n",
    "                                # print(cards[rest[0]], cards[rest[1]])\n",
    "                                # print(calculate(cards[rest[0]], cards[rest[1]]))\n",
    "                                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        if not nums: return False\n",
    "        def helper(nums):\n",
    "            if len(nums) == 1: return abs(nums[0]-24) < 1e-6\n",
    "            for i in range(len(nums)):\n",
    "                for j in range(len(nums)):\n",
    "                    if i != j:\n",
    "                        newnums = [nums[k] for k in range(len(nums)) if i != k != j]\n",
    "                        if helper(newnums + [nums[i]+nums[j]]): return True\n",
    "                        if helper(newnums + [nums[i]-nums[j]]): return True\n",
    "                        if helper(newnums + [nums[i]*nums[j]]): return True\n",
    "                        if nums[j] != 0 and helper(newnums + [nums[i]/nums[j]]): return True\n",
    "            return False\n",
    "        return helper(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0) # 摸一张 (queue 操作)\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0) # 再摸一张 (queue 操作)\n",
    "                for value in [a + b, a - b, a * b, b and a / b]: # 算一下\n",
    "                    cards.append(value) # 记下来 (stack 操作)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop() # (stack 操作)\n",
    "                cards.append(b) # (queue 操作)\n",
    "            cards.append(a) # (queue 操作)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        import copy\n",
    "        def compute(a, b):\n",
    "            return a + b, a - b, a * b, a / (b+1e-9)\n",
    "\n",
    "        def dfs(cards: List[int]) -> bool:\n",
    "            n = len(cards)\n",
    "            if n == 1 and abs(cards[0] - 24) < 1e-5:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i != j:\n",
    "                        for new_element in compute(cards[i], cards[j]):\n",
    "                            new_cards = copy.deepcopy(cards)\n",
    "                            new_cards.pop(max(i, j))\n",
    "                            new_cards.pop(min(i, j))\n",
    "                            new_cards.append(new_element)\n",
    "                            if dfs(new_cards):\n",
    "                                return True\n",
    "            return False\n",
    "\n",
    "        return dfs(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0) \n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0) \n",
    "                comb = [a + b, a - b, a * b, b and a/b]\n",
    "                for value in comb: \n",
    "                    cards.append(value) \n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop() \n",
    "                cards.append(b) \n",
    "            cards.append(a) \n",
    "        return False\n",
    "\n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards)==1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0)\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0)\n",
    "                for value in [a+b, a-b, a*b, b and a/b]:\n",
    "                    cards.append(value)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        # 列表选两个数，计算之后放回新列表，然后继续dfs, 直到只剩一个数，然后判断\n",
    "        def dfs(nums):\n",
    "            target, eps=24, 1e-6\n",
    "            add, subs, mul, did=0, 1, 2, 3\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums)==1:\n",
    "                return abs(nums[0]-target)<eps\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i!=j:\n",
    "                        new_nums=[]\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k!=i and k!=j:\n",
    "                                new_nums.append(z)\n",
    "                        for op in range(4):\n",
    "                            if op in [0, 2] and i>j:# + *满足交换律\n",
    "                                continue\n",
    "                            if op==0:\n",
    "                                new_nums.append(x+y)\n",
    "                            if op==1:\n",
    "                                new_nums.append(x-y)\n",
    "                            if op==2:\n",
    "                                new_nums.append(x*y)\n",
    "                            if op==3:\n",
    "                                if y<eps:\n",
    "                                    continue\n",
    "                                new_nums.append(x/y)\n",
    "                            if dfs(new_nums):\n",
    "                                return True\n",
    "                            new_nums.pop()\n",
    "            return False\n",
    "        return dfs(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSILON = 1e-6\n",
    "        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3\n",
    "\n",
    "        def solve(nums: List[float]) -> bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                return abs(nums[0] - TARGET) < EPSILON\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i != j:\n",
    "                        newNums = list()\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k != i and k != j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k < 2 and i > j:\n",
    "                                continue\n",
    "                            if k == ADD:\n",
    "                                newNums.append(x + y)\n",
    "                            elif k == MULTIPLY:\n",
    "                                newNums.append(x * y)\n",
    "                            elif k == SUBTRACT:\n",
    "                                newNums.append(x - y)\n",
    "                            elif k == DIVIDE:\n",
    "                                if abs(y) < EPSILON:\n",
    "                                    continue\n",
    "                                newNums.append(x / y)\n",
    "                            if solve(newNums):\n",
    "                                return True\n",
    "                            newNums.pop()\n",
    "            return False\n",
    "\n",
    "        return solve(nums)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        n = len(cards)\n",
    "        if n == 0:\n",
    "            return False\n",
    "        if n == 1:\n",
    "            return abs(cards[0] - 24) < 1e-6\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                new_cards = [cards[c] for c in range(n) if c != i and c != j]\n",
    "                for op in (\"+\", \"-\", \"*\", \"/\"):\n",
    "                    if op == \"+\":\n",
    "                        if i > j:\n",
    "                            continue\n",
    "                        else:\n",
    "                            val = cards[i] + cards[j]\n",
    "                    if op == '*':\n",
    "                        if i > j:\n",
    "                            continue\n",
    "                        else:\n",
    "                            val = cards[i] * cards[j]\n",
    "                    if op == '/':\n",
    "                        if cards[j] == 0:\n",
    "                            continue\n",
    "                        else:\n",
    "                            val = cards[i] / cards[j]\n",
    "                    if op == '-':\n",
    "                        val = cards[i] - cards[j]\n",
    "                    new_cards.append(val)\n",
    "                    if self.judgePoint24(new_cards):\n",
    "                        return True\n",
    "                    new_cards.pop()\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        if len(nums)==1:\n",
    "            return abs(24-nums[0])<=10**(-10)\n",
    "    # 每次把计算结果 和之前nums数组中其他元素组成的列表concate起来 作为新的nums 向下递归\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if self.judgePoint24([nums[i]+nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if self.judgePoint24([nums[i]*nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if self.judgePoint24([nums[i]-nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if self.judgePoint24([nums[j]-nums[i]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if nums[j]!=0 and self.judgePoint24([nums[i]/nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]):\n",
    "                    return True\n",
    "                if nums[i]!=0 and self.judgePoint24([nums[j]/nums[i]]+nums[0:i]+nums[i+1:j]+nums[j+1:]):\n",
    "                    return True\n",
    "        # 走到这一步 说明之前都不行\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0)\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0)\n",
    "                for val in [a + b, a - b, b and a / b, a * b]:\n",
    "                    cards.append(val)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3\n",
    "        def backtrack(nums):\n",
    "            if len(nums) == 1:\n",
    "                return math.isclose(nums[0], 24) == True\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i != j:\n",
    "                        newNums = []\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k != i and k != j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k == ADD:\n",
    "                                newNums.append(x + y)\n",
    "                            elif k == MULTIPLY:\n",
    "                                newNums.append(x * y)\n",
    "                            elif k == SUBTRACT:\n",
    "                                newNums.append(x - y)\n",
    "                            elif k == DIVIDE:\n",
    "                                newNums.append(y and x / y)\n",
    "                            if backtrack(newNums):\n",
    "                                return True\n",
    "                            newNums.pop()\n",
    "            return False\n",
    "        return backtrack(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        if len(nums)==1:\n",
    "            return abs(24-nums[0])<=1e-6\n",
    "    # 每次把计算结果 和之前nums数组中其他元素组成的列表concate起来 作为新的nums 向下递\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if self.judgePoint24([nums[i]+nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if self.judgePoint24([nums[i]*nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if self.judgePoint24([nums[i]-nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if self.judgePoint24([nums[j]-nums[i]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): \n",
    "                    return True\n",
    "                if nums[j]!=0 and self.judgePoint24([nums[i]/nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]):\n",
    "                    return True\n",
    "                if nums[i]!=0 and self.judgePoint24([nums[j]/nums[i]]+nums[0:i]+nums[i+1:j]+nums[j+1:]):\n",
    "                    return True\n",
    "    # 走到这一步 说明之前都不行\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def dfs():\n",
    "            if len(cards) == 1 and abs(cards[0] - 24)<0.00001:\n",
    "                return True\n",
    "            for x in cards.copy():\n",
    "                cards.remove(x)\n",
    "                for y in cards.copy():\n",
    "                    cards.remove(y)\n",
    "                    cards.append(x + y)\n",
    "                    if dfs():return True\n",
    "                    cards.remove(x + y)\n",
    "                    cards.append(x - y)\n",
    "                    if dfs():return True\n",
    "                    cards.remove(x - y)\n",
    "                    cards.append(x * y)\n",
    "                    if dfs():return True\n",
    "                    cards.remove(x * y)\n",
    "                    if y!=0:\n",
    "                        cards.append(x / y)\n",
    "                        if dfs():return True\n",
    "                        cards.remove(x / y)\n",
    "                    if x != 0:\n",
    "                        cards.append(y / x)\n",
    "                        if dfs():return True\n",
    "                        cards.remove(y / x)\n",
    "                    cards.append(y - x)\n",
    "                    if dfs():return True\n",
    "                    cards.remove(y - x)\n",
    "                    cards.append(y)\n",
    "                cards.append(x)\n",
    "            return False\n",
    "\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def calculate(num1,num2):\n",
    "            return set([num1*num2,num1/num2 if num2 != 0 else 0,num2/num1 if num1 != 0 else 0,num1-num2,num2-num1,num1+num2])\n",
    "        #cards = [8,1,6,6]\n",
    "        for i in range(1,4):\n",
    "            rest = [j for j in range(1,4) if j != i]\n",
    "            set1 = calculate(cards[0], cards[i])\n",
    "            set2 = calculate(cards[rest[0]], cards[rest[1]])\n",
    "            for num1 in set1:\n",
    "                for num2 in set2:\n",
    "                    for num in calculate(num1, num2):\n",
    "                        if (abs(num) - 24)**2 <= 0.001:\n",
    "                            #print(i)\n",
    "                            return True\n",
    "        for i in range(4):\n",
    "            for j in range(4):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                rest = [k for k in range(4) if (k != i and k != j)]\n",
    "                for num2 in calculate(cards[rest[0]], cards[rest[1]]):\n",
    "                    for num1 in calculate(cards[j], num2):\n",
    "                        for num in calculate(cards[i], num1):\n",
    "                            if (abs(num) - 24)**2 <= 0.001:\n",
    "                                # print(cards[i],num1)\n",
    "                                # print(calculate(cards[i], num1))\n",
    "                                # print(cards[j], num2)\n",
    "                                # print(calculate(cards[j], num2))\n",
    "                                # print(cards[rest[0]], cards[rest[1]])\n",
    "                                # print(calculate(cards[rest[0]], cards[rest[1]]))\n",
    "                                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "\n",
    "        \n",
    "        lc = len(cards)\n",
    "        if lc == 1:\n",
    "            if -0.00001< cards[0] - 24<0.00001: return True\n",
    "\n",
    "        for _ in range(lc):\n",
    "            a = cards.pop(0)\n",
    "            for _ in range(lc-1):\n",
    "                b = cards.pop(0)\n",
    "\n",
    "                for c in [a+b, a-b, a*b, b and a/b]:\n",
    "                    cards.append(c)\n",
    "                    if self.judgePoint24(cards): return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "        return False\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def backtrack(path):\n",
    "            if len(path) == 1 and abs(path[0] - 24) < 10e-6:\n",
    "                return True\n",
    "            for i in range(0, len(path)):\n",
    "                for j in range(0, len(path)):\n",
    "                    if i==j: continue\n",
    "                    newpath = path.copy()\n",
    "                    newpath.pop(max(i,j))\n",
    "                    newpath.pop(min(i,j))\n",
    "                    for op in ['+', '-', '*', '/']:\n",
    "                        if op == '/' and path[j] == 0: continue\n",
    "                        if backtrack(newpath+[eval(str(path[i])+op+str(path[j]))]): return True\n",
    "            return False\n",
    "        return backtrack(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "            # 判断是否能够通过运算得到24\n",
    "        def search(numbers):\n",
    "            # 如果只剩一个数，检查它是否接近24\n",
    "            if len(numbers) == 1:\n",
    "                return abs(numbers[0] - 24) < 1e-6\n",
    "\n",
    "            # 尝试所有的配对\n",
    "            for i in range(len(numbers)):\n",
    "                for j in range(len(numbers)):\n",
    "                    if i != j:\n",
    "                        # 对于每一对配对，尝试每种运算\n",
    "                        for op in [add, sub, mul, truediv]:\n",
    "                            if (op in [add, mul] and i >= j):\n",
    "                                continue\n",
    "                            # 除法运算需要注意除数不为零\n",
    "                            if op is truediv and numbers[j] == 0:\n",
    "                                continue\n",
    "                            next_numbers = [numbers[k] for k in range(len(numbers)) if k != i and k != j]\n",
    "                            next_numbers.append(op(numbers[i], numbers[j]))\n",
    "                            if search(next_numbers):\n",
    "                                return True\n",
    "            return False\n",
    "\n",
    "        # 尝试所有数字的排列组合\n",
    "        for perm in permutations(cards):\n",
    "            if search(list(perm)):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSILON = 1e-6\n",
    "        ADD, MULTIPLY,SUBTRACT,DIVIDE = 0, 1, 2, 3\n",
    "\n",
    "        def solve(nums: List[float])->bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                return abs(nums[0] - TARGET) < EPSILON\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i != j:\n",
    "                        newNums = list()\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k != i and k != j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k < 2 and i > j:\n",
    "                                continue\n",
    "                            if k == ADD:\n",
    "                                newNums.append(x + y)\n",
    "                            elif k == MULTIPLY:\n",
    "                                newNums.append(x * y)\n",
    "                            elif k == SUBTRACT:\n",
    "                                newNums.append(x - y)\n",
    "                            elif k == DIVIDE:\n",
    "                                if abs(y) < EPSILON:\n",
    "                                    continue\n",
    "                                newNums.append(x / y)\n",
    "                            if solve(newNums):\n",
    "                                return True\n",
    "                            newNums.pop()\n",
    "            return False\n",
    "        return solve(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        arr = []\n",
    "        for i in range(4):\n",
    "            arr.append(float(cards[i]))\n",
    "        return self.dfs(arr)\n",
    "    def dfs(self, arr:List[float]) -> bool:\n",
    "        if len(arr) == 1:\n",
    "            return arr[0] > 23.99 and arr[0] < 24.01\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                nextarr = []\n",
    "\n",
    "                for k in range(n):\n",
    "                    if k == i or k == j:\n",
    "                        continue\n",
    "                    nextarr.append(arr[k])\n",
    "\n",
    "                res = False\n",
    "                \n",
    "                nextarr.append(arr[i] + arr[j])\n",
    "                res = self.dfs(nextarr) or res\n",
    "                if res: return True\n",
    "                nextarr = nextarr[:-1]\n",
    "                nextarr.append(arr[i] - arr[j])\n",
    "                res = self.dfs(nextarr) or res\n",
    "                if res: return True\n",
    "                nextarr = nextarr[:-1]\n",
    "                nextarr.append(arr[i] * arr[j])\n",
    "                res = self.dfs(nextarr) or res\n",
    "                if res: return True\n",
    "                nextarr = nextarr[:-1]\n",
    "                arr[j] = arr[j]+1e-5 if arr[j] == 0 else arr[j]\n",
    "                nextarr.append(arr[i] / arr[j])\n",
    "                res = self.dfs(nextarr) or res\n",
    "                if res: return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, A: List[int]) -> bool:\n",
    "\n",
    "        if not A: return False\n",
    "\n",
    "        def dfs(A):\n",
    "            if len(A) == 1 and abs(A[0]-24) < 1e-6: return True\n",
    "            for i in range(len(A)):\n",
    "                for j in range(len(A)):\n",
    "                    if i != j:\n",
    "                        rest = [A[x] for x in range(len(A)) if i != x != j]\n",
    "                        if dfs(rest + [A[i] + A[j]]): return True\n",
    "                        if dfs(rest + [A[i] - A[j]]): return True\n",
    "                        if dfs(rest + [A[i] * A[j]]): return True\n",
    "                        if A[j] != 0 and dfs(rest + [A[i] / A[j]]): return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(A)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not A:\n",
    "        #     return False\n",
    "        \n",
    "        # def dfs(A):\n",
    "        #     if len(A) == 1:\n",
    "        #         return abs(A[0] - 24) < 1e-6\n",
    "\n",
    "        #     for i in range(len(A)):\n",
    "        #         for j in range(len(A)):\n",
    "        #             if i != j:\n",
    "        #                 rest = [A[k] for k in range(len(A)) if i != k != j]\n",
    "        #                 if dfs(rest + [A[i] + A[j]]): return True\n",
    "        #                 if dfs(rest + [A[i] - A[j]]): return True\n",
    "        #                 if dfs(rest + [A[i] * A[j]]): return True\n",
    "        #                 if A[j] != 0 and dfs(rest + [A[i] / A[j]]): return True\n",
    "        #     return False\n",
    "        # return dfs(A)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def dfs(cards:List[float]):\n",
    "            if len(cards) == 1:\n",
    "                return (abs(cards[0]-24) < 1e-6)\n",
    "            for i in range(len(cards)-1):\n",
    "                for j in range(i+1,len(cards)):\n",
    "                    res = []\n",
    "                    for l in range(len(cards)):\n",
    "                        if l != i and l != j:\n",
    "                            res.append(cards[l])\n",
    "                    if dfs(res+[cards[i]+cards[j]]):\n",
    "                        return True\n",
    "                    elif dfs(res+[cards[i]-cards[j]]):\n",
    "                        return True\n",
    "                    elif dfs(res+[cards[j]-cards[i]]):\n",
    "                        return True\n",
    "                    elif dfs(res+[cards[i]*cards[j]]):\n",
    "                        return True\n",
    "                    elif cards[j]!= 0 and dfs(res+[cards[i]/cards[j]]):\n",
    "                        return True\n",
    "                    elif cards[i] != 0 and dfs(res+[cards[j]/cards[i]]):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(cards)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0],24)\n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0)  # 拿出第一张\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0) # 再拿出一张\n",
    "                for value in [a+b,a-b,a*b, b and a/b]:\n",
    "                     #将其中两张牌分别用多种分发合并为一张牌，并判断\n",
    "                    cards.append(value)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSILON = 1e-6\n",
    "        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3\n",
    "\n",
    "        def solve(nums: List[float]) -> bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                return abs(nums[0] - TARGET) < EPSILON\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    # 取两个不同的数：\n",
    "                    if i != j:\n",
    "                        newNums = list()\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k != i and k != j:\n",
    "                                # 把未取剩下的数保存在 newNums 中：\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k < 2 and i > j:\n",
    "                                continue\n",
    "                            if k == ADD:\n",
    "                                newNums.append(x + y)\n",
    "                            elif k == MULTIPLY:\n",
    "                                newNums.append(x * y)\n",
    "                            elif k == SUBTRACT:\n",
    "                                newNums.append(x - y)\n",
    "                            elif k == DIVIDE:\n",
    "                                if abs(y) < EPSILON:\n",
    "                                    continue\n",
    "                                newNums.append(x / y)\n",
    "                            if solve(newNums):\n",
    "                                print(x, k, y)\n",
    "                                return True\n",
    "                            newNums.pop()\n",
    "            return False\n",
    "\n",
    "        return solve(cards)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return abs(cards[0] - 24) <= 1e-6\n",
    "        for i in range(len(cards)):\n",
    "            for j in range(i + 1, len(cards)):\n",
    "                a, b = cards[i], cards[j]\n",
    "                cutted = cards[:i] + cards[i + 1 : j] + cards[j + 1 :]\n",
    "                if (\n",
    "                    self.judgePoint24(cutted + [a + b])\n",
    "                    or self.judgePoint24(cutted + [a - b])\n",
    "                    or self.judgePoint24(cutted + [b - a])\n",
    "                    or self.judgePoint24(cutted + [a * b])\n",
    "                    or (b != 0 and self.judgePoint24(cutted + [a / b]))\n",
    "                    or (a != 0 and self.judgePoint24(cutted + [b / a]))\n",
    "                ):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        MIN_OFFSET = 10**(-6)\n",
    "        def calculate(a,b):\n",
    "            possible_number = [a+b,a-b, a*b]\n",
    "            if abs(a)>MIN_OFFSET:possible_number.append(b/a)\n",
    "            if abs(b)>MIN_OFFSET:possible_number.append(a/b)\n",
    "            return set(possible_number)\n",
    "\n",
    "        for i in range(4):\n",
    "            a= cards[i]\n",
    "            for j in range(4):\n",
    "                b =cards[j]\n",
    "                if i==j:continue\n",
    "\n",
    "                for cur_c in calculate(*[cards[k] for k in range(4) if (k not in [i,j])]):\n",
    "                    # (ab)c\n",
    "                    for cur_a in  calculate(a,b):\n",
    "                        for result in calculate(cur_a, cur_c):\n",
    "                            if abs(result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "                    # a(bc)\n",
    "                    for cur_b in calculate(b,cur_c):\n",
    "                        for result in calculate(a, cur_b):\n",
    "                            if abs(result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "        return False\n",
    "\n",
    "                \n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards)==1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0)\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0)\n",
    "                for value in [a+b, a-b, a*b, b and a/b]:\n",
    "                    cards.append(value)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                start=0 if op in ('/','-') else i+1\n",
    "                for j in range(start,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    if op=='+':\n",
    "                        num=arr[i]+arr[j]\n",
    "                    elif op=='-':\n",
    "                        num=arr[i]-arr[j]\n",
    "                    elif op=='*':\n",
    "                        num=arr[i]*arr[j]\n",
    "                    else:\n",
    "                        num=arr[i]/arr[j]\n",
    "                    # num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def calculate(num1,num2):\n",
    "            return set([num1*num2,num1/num2 if num2 != 0 else 0,num2/num1 if num1 != 0 else 0,num1-num2,num1+num2])\n",
    "        #cards = [8,1,6,6]\n",
    "        for i in range(1,4):\n",
    "            rest = [j for j in range(1,4) if j != i]\n",
    "            set1 = calculate(cards[0], cards[i])\n",
    "            set2 = calculate(cards[rest[0]], cards[rest[1]])\n",
    "            for num1 in set1:\n",
    "                for num2 in set2:\n",
    "                    for num in calculate(num1, num2):\n",
    "                        if (abs(num) - 24)**2 <= 0.001:\n",
    "                            #print(i)\n",
    "                            return True\n",
    "        for i in range(4):\n",
    "            for j in range(4):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                rest = [k for k in range(4) if (k != i and k != j)]\n",
    "                for num2 in calculate(cards[rest[0]], cards[rest[1]]):\n",
    "                    for num1 in calculate(cards[j], num2):\n",
    "                        for num in calculate(cards[i], num1):\n",
    "                            if (abs(num) - 24)**2 <= 0.001:\n",
    "                                # print(cards[i],num1)\n",
    "                                # print(calculate(cards[i], num1))\n",
    "                                # print(cards[j], num2)\n",
    "                                # print(calculate(cards[j], num2))\n",
    "                                # print(cards[rest[0]], cards[rest[1]])\n",
    "                                # print(calculate(cards[rest[0]], cards[rest[1]]))\n",
    "                                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                start=0 if op in ('/','-') else i+1\n",
    "                for j in range(start,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    if op=='+':\n",
    "                        num=arr[i]+arr[j]\n",
    "                    elif op=='-':\n",
    "                        num=arr[i]-arr[j]\n",
    "                    elif op=='*':\n",
    "                        num=arr[i]*arr[j]\n",
    "                    else:\n",
    "                        num=arr[i]/arr[j]\n",
    "                    # num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        tol = 1e-6\n",
    "        a0 = float(cards[0])\n",
    "        a1 = float(cards[1])\n",
    "        a2 = float(cards[2])\n",
    "        a3 = float(cards[3])\n",
    "        def divide(a, b):\n",
    "            if b == 0:\n",
    "                return None\n",
    "            return a / b\n",
    "\n",
    "        def submultiplyDouble(a,b,c,d,K):\n",
    "            if (a+b)*(d+c)==K or abs(a-b)*abs(d-c)==K or abs(a+b)*abs(c-d)==K or abs(a-b)*abs(c-d)==K:\n",
    "                return True\n",
    "            return False\n",
    "        def multiplyDouble(a,b,c,d,K):\n",
    "            if submultiplyDouble(a,b,c,d,K) or submultiplyDouble(a,c,b,d,K) or submultiplyDouble(a,d,b,c,K):\n",
    "                return True\n",
    "            return False\n",
    "        def subdivideDouble(a,b,c,d,K):\n",
    "            if divide((a+b),(d+c))==K or divide(abs(a-b),abs(d-c))==K or divide(abs(a+b),abs(c-d))==K or divide(abs(a-b),abs(c-d))==K:\n",
    "                return True\n",
    "            if divide((d+c),(a+b))==K or divide(abs(d-c),abs(a-b))==K or divide(abs(c-d),abs(a+b))==K or divide(abs(c-d),abs(a-b))==K:\n",
    "                return True\n",
    "            return False   \n",
    "        def divideDouble(a,b,c,d,K):\n",
    "            if subdivideDouble(a,b,c,d,K) or subdivideDouble(a,c,b,d,K) or subdivideDouble(a,d,b,c,K):\n",
    "                return True\n",
    "            return False         \n",
    "\n",
    "        def subdoubleMultiply(a,b,c,d,K):\n",
    "            if a*b+c*d==K or abs(a*b-c*d)==K:\n",
    "                return True\n",
    "            return False\n",
    "        def subdoubleDivide(a,b,c,d,K):\n",
    "            if a/b+c/d==K or abs(a/b-c/d)==K or b/a+c/d==K or abs(b/a-c/d)==K or a/b+d/c==K or abs(a/b-d/c)==K or b/a+d/c==K or abs(b/a-d/c)==K:\n",
    "                return True\n",
    "            return False\n",
    "        def doubleMultiply(a,b,c,d,K):\n",
    "            if subdoubleMultiply(a,b,c,d,K) or subdoubleMultiply(a,c,b,d,K) or subdoubleMultiply(a,d,b,c,K):\n",
    "                return True\n",
    "            return False\n",
    "        def doubleDivide(a,b,c,d,K):\n",
    "            if subdoubleDivide(a,b,c,d,K) or subdoubleDivide(a,c,b,d,K) or subdoubleDivide(a,d,b,c,K):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        def twoPoint(a,b,K):\n",
    "            if abs(a+b-K)<tol or abs(a*b-K)<tol or abs(abs(a-b)-K)<tol or abs(a/b-K)<tol or abs(b/a-K)<tol:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def subthreePoint(a,b,c,K):\n",
    "            if twoPoint(a,b,abs(K-c)) or twoPoint(a,b,K+c) or twoPoint(a,b,K*c) or twoPoint(a,b,K/c) or twoPoint(a,b,c/K):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        def threePoint(a,b,c,K):\n",
    "            if subthreePoint(a,b,c,K) or subthreePoint(a,c,b,K) or subthreePoint(b,c,a,K):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        def subfourPoint(a,b,c,d,K):\n",
    "            if threePoint(a,b,c,abs(K-d)) or threePoint(a,b,c,K+d) or threePoint(a,b,c,K*d) or threePoint(a,b,c,K/d) or threePoint(a,b,c,d/K):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def fourPoint(a,b,c,d,K=24):\n",
    "            if subfourPoint(a,b,c,d,K) or subfourPoint(a,b,d,c,K) or subfourPoint(a,c,d,b,K) or subfourPoint(b,c,d,a,K):\n",
    "                return True\n",
    "            if doubleDivide(a,b,c,d,K):\n",
    "                return True\n",
    "            if doubleMultiply(a,b,c,d,K):\n",
    "                return True\n",
    "            if divideDouble(a,b,c,d,K):\n",
    "                return True\n",
    "            if multiplyDouble(a,b,c,d,K):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        return fourPoint(a0,a1,a2,a3)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        # 24 = a * b = a + b = a // b\n",
    "        def cal(a, b):\n",
    "            ans = []\n",
    "            ans.append(a + b)\n",
    "            ans.append(a - b)\n",
    "            ans.append(b - a)\n",
    "            ans.append(a * b)\n",
    "            if a: ans.append(b / a)\n",
    "            if b: ans.append(a / b)\n",
    "            return ans\n",
    "        # eps = 1e-6\n",
    "        def dfs(a):\n",
    "            n = len(a)\n",
    "            if n == 1: \n",
    "                return math.isclose(a[0], 24)\n",
    "                # return abs(a[0] - 24) <= eps\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    na = []\n",
    "                    for k in range(n):\n",
    "                        if k != i and k != j:\n",
    "                            na.append(a[k])\n",
    "                    # print(f'na={na}')\n",
    "                    for v in cal(a[i], a[j]):\n",
    "                        if dfs(na + [v]):\n",
    "                            return True\n",
    "            return False\n",
    "        return dfs(cards)\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        if not nums: return False\n",
    "        def helper(nums):\n",
    "            if len(nums) == 1: return abs(nums[0]-24) < 1e-6\n",
    "            for i in range(len(nums)):\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    newnums = [nums[k] for k in range(len(nums)) if i != k != j]\n",
    "                    if helper(newnums + [nums[i]+nums[j]]): return True\n",
    "                    if helper(newnums + [nums[i]*nums[j]]): return True\n",
    "                    if helper(newnums + [nums[i]-nums[j]]): return True\n",
    "                    if helper(newnums + [nums[j]-nums[i]]): return True\n",
    "                    if nums[j] != 0 and helper(newnums + [nums[i]/nums[j]]): return True\n",
    "                    if nums[i] != 0 and helper(newnums + [nums[j]/nums[i]]): return True\n",
    "            return False\n",
    "        return helper(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import truediv, mul, add, sub\n",
    "\n",
    "class Solution(object):\n",
    "    def judgePoint24(self, A):\n",
    "        if not A: return False\n",
    "        if len(A) == 1: return abs(A[0] - 24) < 1e-6\n",
    "\n",
    "        for i in range(len(A)):\n",
    "            for j in range(len(A)):\n",
    "                if i != j:\n",
    "                    B = [A[k] for k in range(len(A)) if i != k != j]\n",
    "                    for op in (truediv, mul, add, sub):\n",
    "                        if (op is add or op is mul) and j > i: continue\n",
    "                        if op is not truediv or A[j]:\n",
    "                            B.append(op(A[i], A[j]))\n",
    "                            if self.judgePoint24(B): return True\n",
    "                            B.pop()\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSILON = 1e-6\n",
    "        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3\n",
    "\n",
    "        def solve(nums: List[float]) -> bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                return abs(nums[0] - TARGET) < EPSILON\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i != j:\n",
    "                        newNums = list()\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k != i and k != j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k < 2 and i > j:\n",
    "                                continue\n",
    "                            if k == ADD:\n",
    "                                newNums.append(x + y)\n",
    "                            elif k == MULTIPLY:\n",
    "                                newNums.append(x * y)\n",
    "                            elif k == SUBTRACT:\n",
    "                                newNums.append(x - y)\n",
    "                            elif k == DIVIDE:\n",
    "                                if abs(y) < EPSILON:\n",
    "                                    continue\n",
    "                                newNums.append(x / y)\n",
    "                            if solve(newNums):\n",
    "                                return True\n",
    "                            newNums.pop()\n",
    "            return False\n",
    "\n",
    "        return solve(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        # 24 = a * b = a + b = a // b\n",
    "        def cal(a, b):\n",
    "            ans = []\n",
    "            ans.append(a + b)\n",
    "            ans.append(a - b)\n",
    "            ans.append(b - a)\n",
    "            ans.append(a * b)\n",
    "            if a: ans.append(b / a)\n",
    "            if b: ans.append(a / b)\n",
    "            return ans\n",
    "        # eps = 1e-6\n",
    "        def dfs(a):\n",
    "            n = len(a)\n",
    "            if n == 1: \n",
    "                return abs(a[0] - 24) < 0.000001\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    na = a[:i] + a[i+1:j] + a[j+1:]\n",
    "                    # print(f'na={na}')\n",
    "                    for v in cal(a[i], a[j]):\n",
    "                        if dfs(na + [v]):\n",
    "                            return True\n",
    "            return False\n",
    "        return dfs(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        ops = ['+','-1','-2','*','/1','/2']\n",
    "        cards = [(card, str(card)) for card in cards]\n",
    "        def dfs(cards):\n",
    "            n = len(cards)\n",
    "            if n == 1:\n",
    "                if (cards[0][0] - 24)**2 < 0.001:\n",
    "                    return cards[0][1]\n",
    "            for i in range(n):\n",
    "                for j in range(i+1,n):\n",
    "                    new_cards = [cards[k] for k in range(n) if k != i and k != j]\n",
    "                    for op in ops:\n",
    "                        new_card = None\n",
    "                        if op == '+':\n",
    "                            new_card = (cards[i][0] + cards[j][0], '('+cards[i][1]+'+'+cards[j][1]+')')\n",
    "                        elif op == '-1':\n",
    "                            new_card = (cards[i][0] - cards[j][0], '('+cards[i][1]+'-'+cards[j][1]+')')\n",
    "                        elif op == '-2':\n",
    "                            new_card = (cards[j][0] - cards[i][0], '('+cards[j][1]+'-'+cards[i][1]+')')\n",
    "                        elif op == '*':\n",
    "                            new_card = (cards[i][0] * cards[j][0], '('+cards[i][1]+'*'+cards[j][1]+')')\n",
    "                        elif op == '/1' and cards[j][0] != 0:\n",
    "                            new_card = (cards[i][0] / cards[j][0], '('+cards[i][1]+'/'+cards[j][1]+')')\n",
    "                        elif op == '/2' and cards[i][0] != 0:\n",
    "                            new_card = (cards[j][0] / cards[i][0], '('+cards[j][1]+'/'+cards[i][1]+')')\n",
    "                        if new_card:\n",
    "                            ans = dfs([new_card]+new_cards)\n",
    "                            if ans is not None:\n",
    "                                return ans\n",
    "            return None\n",
    "        ans = dfs(cards)\n",
    "        print(ans)\n",
    "        return ans is not None       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                for j in range(0,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        MIN_OFFSET = 10**(-6)\n",
    "        def calculate(a,b):\n",
    "            possible_number = [a+b,a-b, a*b]\n",
    "            if abs(a)>MIN_OFFSET:possible_number.append(b/a)\n",
    "            if abs(b)>MIN_OFFSET:possible_number.append(a/b)\n",
    "            return set(possible_number)\n",
    "\n",
    "\n",
    "        # number_set = set()\n",
    "        for i in range(4):\n",
    "            a= cards[i]\n",
    "            for j in range(4):\n",
    "                b =cards[j]\n",
    "                if i==j:continue\n",
    "                possible_set = calculate(*[cards[k] for k in range(4) if (k not in [i,j])])\n",
    "\n",
    "                for cur_c in possible_set:\n",
    "                    \n",
    "                    # (ab)c\n",
    "                    for new_a in  calculate(a,b):\n",
    "                        for cur_result in calculate(new_a, cur_c):\n",
    "                            if abs(cur_result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "\n",
    "                    for new_b in calculate(b,cur_c):\n",
    "                        for cur_result in calculate(a, new_b):\n",
    "                            if abs(cur_result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "        return False\n",
    "\n",
    "                \n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "            # 判断是否能够通过运算得到24\n",
    "        def search(numbers):\n",
    "            # 如果只剩一个数，检查它是否接近24\n",
    "            if len(numbers) == 1:\n",
    "                return abs(numbers[0] - 24) < 1e-6\n",
    "\n",
    "            # 尝试所有的配对\n",
    "            for i in range(len(numbers)):\n",
    "                for j in range(len(numbers)):\n",
    "                    if i != j:\n",
    "                        # 对于每一对配对，尝试每种运算\n",
    "                        for op in [add, sub, mul, truediv]:\n",
    "                            if (op in [add, mul] and i >= j):\n",
    "                                continue\n",
    "                            # 除法运算需要注意除数不为零\n",
    "                            if op is truediv and numbers[j] == 0:\n",
    "                                continue\n",
    "                            next_numbers = [numbers[k] for k in range(len(numbers)) if k != i and k != j]\n",
    "                            next_numbers.append(op(numbers[i], numbers[j]))\n",
    "                            if search(next_numbers):\n",
    "                                return True\n",
    "            return False\n",
    "\n",
    "        # 尝试所有数字的排列组合\n",
    "        # for perm in permutations(cards):\n",
    "        #     if search(list(perm)):\n",
    "        #         return True\n",
    "        return search(cards)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0) # 摸一张 (queue 操作)\n",
    "            for _ in range(len(cards)):\n",
    "                b = cards.pop(0) # 再摸一张 (queue 操作)\n",
    "                for value in [a + b, a - b, a * b, b and a / b]: # 算一下\n",
    "                    cards.append(value) # 记下来 (stack 操作)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop() # (stack 操作)\n",
    "                cards.append(b) # (queue 操作)\n",
    "            cards.append(a) # (queue 操作)\n",
    "        return False\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSLION = 1e-6\n",
    "        ADD, MULIPLY, SUBTRACT, DIVIDE = 0,1,2,3\n",
    "\n",
    "        def dfs(nums:List[int])->bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums)==1:\n",
    "                return abs(TARGET - nums[0])<EPSLION\n",
    "            \n",
    "            for i,x in enumerate(nums):\n",
    "                for j,y in enumerate(nums):\n",
    "                    if i!=j:\n",
    "                        newNums = []\n",
    "                        for k,z in enumerate(nums):\n",
    "                            if k!=i and k!=j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k<2 and i>j:\n",
    "                                continue\n",
    "                            if k==ADD:\n",
    "                                newNums.insert(0, x+y)\n",
    "                            elif k == MULIPLY:\n",
    "                                newNums.insert(0, x*y)\n",
    "                            elif k==SUBTRACT:\n",
    "                                newNums.insert(0, x-y)\n",
    "                            elif k==DIVIDE:\n",
    "                                if abs(y)<EPSLION:\n",
    "                                    continue\n",
    "                                newNums.insert(0, x/y)\n",
    "                            if dfs(newNums):\n",
    "                                return True\n",
    "                            newNums.pop(0)\n",
    "            return False\n",
    "        return dfs(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "\n",
    "        TARGET = 24\n",
    "        EPSILON = 1e-6\n",
    "\n",
    "        def solve(nums):\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                return abs(nums[0]-TARGET) < EPSILON\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    \n",
    "                    tmp = []\n",
    "                    for k, z in enumerate(nums):\n",
    "                        if i == k or j == k:\n",
    "                            continue\n",
    "                        tmp.append(z)\n",
    "                \n",
    "                    for k in range(4):\n",
    "                        if k < 2 and i > j:\n",
    "                            continue\n",
    "                        if k == 0:\n",
    "                            tmp.append(x+y)\n",
    "                        elif k == 1:\n",
    "                            tmp.append(x*y)\n",
    "                        elif k == 2:\n",
    "                            tmp.append(x-y)\n",
    "                        else:\n",
    "                            if abs(y) < EPSILON:\n",
    "                                continue\n",
    "                            tmp.append(x/y)\n",
    "                        \n",
    "                        if solve(tmp): return True\n",
    "                        tmp.pop()\n",
    "\n",
    "            return False\n",
    "        \n",
    "        return solve(cards)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def getValue(self, a, b):\n",
    "        return [x for x in {a+b, a-b, a*b, b and a/b}]\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def dfs(nums):\n",
    "            if len(nums) == 1:\n",
    "                return math.isclose(nums[0], 24)\n",
    "            ans = False\n",
    "            for a,b, *rest in itertools.permutations(nums):\n",
    "                for x in self.getValue(a, b):\n",
    "                    ans = ans or dfs([x]+rest)\n",
    "            return ans\n",
    "        return dfs(cards)\n",
    "    def judgePoint24_try(self, cards: List[int]) -> bool:\n",
    "        # print(4/(1-2/3))\n",
    "        # 全排列然后每次取前两个进行操作\n",
    "        ops = {\n",
    "            '+': lambda x,y:x+y,\n",
    "            '-': lambda x,y:x-y,\n",
    "            '*': lambda x,y:x*y,\n",
    "            '/': lambda x,y:x/y if y != 0 else float('inf')\n",
    "            }\n",
    "        # candiatesList = itertools.permutations(cards, 4)\n",
    "        # print(f\"candiatesList:{sorted(candiatesList)}\")\n",
    "        # print(f\"candiatesList:{candiatesList}\")\n",
    "        nextCandiatesList = []\n",
    "        for can in itertools.permutations(cards, 4):\n",
    "            a, b, c, d = can\n",
    "            for op in ops.keys():\n",
    "                ab = ops[op](a, b)\n",
    "                if ab != float(\"inf\"):\n",
    "                    nextCandiatesList.append([ab, c, d])\n",
    "                # ba = ops[op](b, a)\n",
    "                # if ba != float(\"inf\"):\n",
    "                    # nextCandiatesList.append([ba, c, d])\n",
    "        # print(f\"nextCandiates:{nextCandiatesList}\")\n",
    "        lastCandiatesList = []\n",
    "        for can in nextCandiatesList:\n",
    "            a, b, c = can\n",
    "            for op in ops.keys():\n",
    "                ab = ops[op](a, b)\n",
    "                if ab != float(\"inf\"):\n",
    "                    lastCandiatesList.append([ab, c])\n",
    "                # ba = ops[op](b, a)\n",
    "                # if ba != float(\"inf\"):\n",
    "                    # lastCandiatesList.append([ba, c])\n",
    "        print(f\"lastList:{lastCandiatesList}\")\n",
    "        for can in lastCandiatesList:\n",
    "            a, b = can\n",
    "            for op in ops.keys():\n",
    "                ans = ops[op](a, b)\n",
    "                if abs(ans - 24) < 0.0001:\n",
    "                    return True\n",
    "                # otherAns = ops[op](b, a)\n",
    "                # if abs(otherAns - 24) < 0.001:\n",
    "                    # return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0],24)\n",
    "\n",
    "        for _ in range(len(cards)):\n",
    "            a = cards.pop(0)\n",
    "            for _ in range(len(cards)):\n",
    "                b =cards.pop(0)\n",
    "                for value in [a+b,a-b,a*b,b and a/b]:\n",
    "                    cards.append(value)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSILON = 1e-6\n",
    "        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3\n",
    "\n",
    "        def solve(nums: List[float]) -> bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                return abs(nums[0] - TARGET) < EPSILON\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i != j:\n",
    "                        newNums = list()\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k != i and k != j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k < 2 and i > j:\n",
    "                                continue\n",
    "                            if k == ADD:\n",
    "                                newNums.append(x + y)\n",
    "                            elif k == MULTIPLY:\n",
    "                                newNums.append(x * y)\n",
    "                            elif k == SUBTRACT:\n",
    "                                newNums.append(x - y)\n",
    "                            elif k == DIVIDE:\n",
    "                                if abs(y) < EPSILON:\n",
    "                                    continue\n",
    "                                newNums.append(x / y)\n",
    "                            if solve(newNums):\n",
    "                                return True\n",
    "                            newNums.pop()\n",
    "            return False\n",
    "\n",
    "        return solve(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        if len(cards) == 1:\n",
    "            return math.isclose(cards[0], 24)\n",
    "        \n",
    "        for i in range(len(cards)):\n",
    "            a = cards.pop(0)\n",
    "            for j in range(len(cards)):\n",
    "                b = cards.pop(0)\n",
    "                for value in [a+b, a-b, a*b, b and a/b]:\n",
    "                    cards.append(value)\n",
    "                    if self.judgePoint24(cards):\n",
    "                        return True\n",
    "                    cards.pop()\n",
    "                cards.append(b)\n",
    "            cards.append(a)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSILON = 1e-6\n",
    "        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3\n",
    "\n",
    "        def solve(nums: List[float], out) -> bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                if abs(nums[0] - TARGET) < EPSILON:\n",
    "                    print(out)\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            for i, x in enumerate(nums):\n",
    "                for j, y in enumerate(nums):\n",
    "                    if i != j:\n",
    "                        newNums = list()\n",
    "                        for k, z in enumerate(nums):\n",
    "                            if k != i and k != j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k < 2 and i > j:\n",
    "                                continue\n",
    "                            if k == ADD:\n",
    "                                t = out + f\"{x}+{y}   \"\n",
    "                                newNums.append(x + y)\n",
    "                            elif k == MULTIPLY:\n",
    "                                t = out + f\"{x}*{y}   \"\n",
    "                                newNums.append(x * y)\n",
    "                            elif k == SUBTRACT:\n",
    "                                t = out + f\"{x}-{y}   \"\n",
    "                                newNums.append(x - y)\n",
    "                            elif k == DIVIDE:\n",
    "                                if abs(y) < EPSILON:\n",
    "                                    continue\n",
    "                                t = out + f\"{x}/{y}   \"\n",
    "                                newNums.append(x / y)\n",
    "                            if solve(newNums, t):\n",
    "                                return True\n",
    "                            newNums.pop()\n",
    "            return False\n",
    "\n",
    "        return solve(nums, \"\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def lt679(cards):\n",
    "            def add(n1,n2):\n",
    "                nome1,de1,nome2,de2=n1[0],n1[1],n2[0],n2[1]\n",
    "                lcm=math.lcm(de1,de2)\n",
    "                nome1*=(lcm//de1)\n",
    "                nome2*=(lcm//de2)\n",
    "                return [nome1+nome2,lcm]\n",
    "            def sub(n1,n2):\n",
    "                nome1, de1, nome2, de2 = n1[0], n1[1], n2[0], n2[1]\n",
    "                lcm = math.lcm(de1, de2)\n",
    "                nome1 *= (lcm // de1)\n",
    "                nome2 *= (lcm // de2)\n",
    "                return [nome1 - nome2, lcm]\n",
    "            def mul(n1,n2):\n",
    "                nome1, de1, nome2, de2 = n1[0], n1[1], n2[0], n2[1]\n",
    "                nome=nome1*nome2\n",
    "                de=de1*de2\n",
    "                gcd=math.gcd(nome,de)\n",
    "                nome//=gcd\n",
    "                de//=gcd\n",
    "                return [nome,de]\n",
    "            def dev(n1,n2):\n",
    "                return mul(n1,[n2[1],n2[0]])\n",
    "            def is_zero(n):\n",
    "                return n[0]==0\n",
    "            def is_24(n):\n",
    "                return n[0]%n[1]==0 and n[0]//n[1]==24\n",
    "            def dfs(nums):\n",
    "                n=len(nums)\n",
    "                if n==1:return is_24(nums[0])\n",
    "                res=[]\n",
    "                for i in range(n-1):\n",
    "                    n1,n2=nums[i],nums[i+1]\n",
    "                    pre,succ=nums[:i],nums[i+2:]\n",
    "                    res.append(dfs(pre+[add(n1,n2)]+succ))\n",
    "                    res.append(dfs(pre+[sub(n1,n2)]+succ))\n",
    "                    res.append(dfs(pre+[mul(n1,n2)]+succ))\n",
    "                    if not is_zero(n2):res.append(dfs(pre+[dev(n1,n2)]+succ))\n",
    "                return any(res)\n",
    "            def get_nums(comb):\n",
    "                return [ [comb[0],1],[comb[1],1],[comb[2],1],[comb[3],1] ]\n",
    "            def arr(nums):\n",
    "                d=defaultdict(int)\n",
    "                for num in nums:d[num]+=1\n",
    "                def dfs2(p):\n",
    "                    if p==0:return [[num] for num in d.keys()]\n",
    "                    res=[]\n",
    "                    for arr in dfs2(p-1):\n",
    "                        for num in nums:\n",
    "                            temp=arr+[num]\n",
    "                            if len(list(filter(lambda x:x==num,arr)))<d[num]:res.append(temp)\n",
    "                    return res\n",
    "                return dfs2(len(nums)-1)\n",
    "\n",
    "            arrs=arr(cards)\n",
    "            for arr in arrs:\n",
    "                nums=get_nums(arr)\n",
    "                if dfs(nums):return True\n",
    "            return False\n",
    "        return lt679(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        return True if self.back(cards) else False\n",
    "\n",
    "    def back(self, nums):\n",
    "        if len(nums) == 1:\n",
    "            if abs(24 - nums[0]) < 1e-6:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                t = nums[:]\n",
    "                one, two = t[i], t[j]\n",
    "                if i > j:\n",
    "                    a, b = j, i\n",
    "                else:\n",
    "                    a, b = i, j\n",
    "                \n",
    "                if self.back(t[:a] + t[a+1:b] + t[b+1:] + [one + two]) or \\\n",
    "                self.back(t[:a] + t[a+1:b] + t[b+1:] + [one - two]) or \\\n",
    "                self.back(t[:a] + t[a+1:b] + t[b+1:] + [one * two]) or \\\n",
    "                two and self.back(t[:a] + t[a+1:b] + t[b+1:] + [one / two]):\n",
    "                    return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def judgePointN(cards: List[int], n: float) -> bool:\n",
    "            l = len(cards)\n",
    "            if l == 1:\n",
    "                return abs(cards[0] - n) < 0.0001\n",
    "            for card in cards:\n",
    "                temp = cards.copy()\n",
    "                temp.remove(card)\n",
    "                find = judgePointN(temp, n + card)\n",
    "                if find:\n",
    "                    return True\n",
    "                find = judgePointN(temp, n - card)\n",
    "                if find:\n",
    "                    return True\n",
    "                find = judgePointN(temp, card - n)\n",
    "                if find:\n",
    "                    return True\n",
    "                find = judgePointN(temp, n * card)\n",
    "                if find:\n",
    "                    return True\n",
    "                find = judgePointN(temp, n / card)\n",
    "                if find:\n",
    "                    return True\n",
    "                if n > 0:\n",
    "                    find = judgePointN(temp, card / n)\n",
    "                    if find:\n",
    "                        return True\n",
    "            return False\n",
    "        if judgePointN(cards, 24):\n",
    "            return True\n",
    "        for i in range(3):\n",
    "            temp = cards[1:].copy()\n",
    "            temp.remove(temp[i])\n",
    "            find = judgePointN(temp, 24 * (cards[0] + cards[i+1]))\n",
    "            if find:\n",
    "                return True\n",
    "            find = judgePointN(temp, 24 / (cards[0] + cards[i+1]))\n",
    "            if find:\n",
    "                return True\n",
    "            if cards[0] == cards[i+1]:\n",
    "                continue\n",
    "            find = judgePointN(temp, 24 / (cards[0] - cards[i+1]))\n",
    "            if find:\n",
    "                return True\n",
    "            find = judgePointN(temp, 24 * (cards[0] - cards[i+1]))\n",
    "            if find:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getgcd(a, b):\n",
    "    while b:\n",
    "        a, b = b, a % b\n",
    "    return a\n",
    "def simplify(num):\n",
    "    if num[0] == 0:\n",
    "        return (0,1)\n",
    "    if num[1] == 1:\n",
    "        return num\n",
    "    a = getgcd(num[0],num[1])\n",
    "    return (num[0]//a,num[1]//a)\n",
    "def add(num1,num2):\n",
    "    a, b = num1\n",
    "    c, d = num2\n",
    "    return simplify((a*d+c*b,b*d))\n",
    "def sub(num1,num2):\n",
    "    a, b = num1\n",
    "    c, d = num2\n",
    "    return simplify((a*d-c*b,b*d))\n",
    "def mul(num1,num2):\n",
    "    a, b = num1\n",
    "    c, d = num2\n",
    "    return simplify((a*c,b*d))\n",
    "def div(num1,num2):\n",
    "    a, b = num1\n",
    "    c, d = num2\n",
    "    return simplify((a*d,b*c))\n",
    "\n",
    "\n",
    "def func2(ans):\n",
    "    n = len(ans)\n",
    "    if n == 1:\n",
    "        return ans[0] == (24,1)\n",
    "    for i in range(n):\n",
    "        temp = ans[:i]+ans[i+1:]\n",
    "        for j in range(len(temp)):\n",
    "            num1 = ans[i]\n",
    "            num2 = temp[j]\n",
    "            a = add(num1,num2)\n",
    "            b = sub(num1, num2)\n",
    "            c = mul(num1, num2)\n",
    "            if func2([a]+temp[:j]+temp[j+1:]):return True\n",
    "            if func2([b]+temp[:j]+temp[j+1:]):return True\n",
    "            if func2([c]+temp[:j]+temp[j+1:]):return True\n",
    "            if num2[0] != 0:\n",
    "                d = div(num1,num2)\n",
    "                if func2([d]+temp[:j]+temp[j+1:]):return True\n",
    "    return False\n",
    "\n",
    "def func1(cards:List[int]):\n",
    "    ans = []\n",
    "    for i in range(len(cards)):\n",
    "        ans.append((cards[i],1))\n",
    "    return func2(ans)\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        return func1(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "def get_24(cards):\n",
    "    cards = [(v, 1) for v in cards]\n",
    "    return func1(cards)\n",
    "\n",
    "def func1(cards):\n",
    "    n = len(cards)\n",
    "    if n == 1:\n",
    "        return cards[0] == (24, 1)\n",
    "    for i in range(n):\n",
    "        for j in range(i+1, n):\n",
    "            tmp = cards[:i]+cards[i+1:j]+cards[j+1:]\n",
    "            if func1(tmp + [plus(cards[i], cards[j])]): return True\n",
    "            if func1(tmp + [minus(cards[i], cards[j])]): return True\n",
    "            if func1(tmp + [minus(cards[j], cards[i])]): return True\n",
    "            if func1(tmp + [multiply(cards[i], cards[j])]): return True\n",
    "            if cards[j][0] and func1(tmp + [div(cards[i], cards[j])]): return True\n",
    "            if cards[i][0] and func1(tmp + [div(cards[j], cards[i])]): return True\n",
    "    return False\n",
    "\n",
    "def plus(card1, card2):\n",
    "    a1, b1 = card1\n",
    "    a2, b2 = card2\n",
    "    return simplify(a1 * b2 + a2 * b1, b1 * b2)\n",
    "\n",
    "def minus(card1, card2):\n",
    "    a1, b1 = card1\n",
    "    a2, b2 = card2\n",
    "    return simplify(a1 * b2 - a2 * b1, b1 * b2)\n",
    "\n",
    "def multiply(card1, card2):\n",
    "    a1, b1 = card1\n",
    "    a2, b2 = card2\n",
    "    return simplify(a1 * a2, b1 * b2)\n",
    "\n",
    "def div(card1, card2):\n",
    "    a1, b1 = card1\n",
    "    a2, b2 = card2\n",
    "    return simplify(a1 * b2, a2 * b1)\n",
    "\n",
    "def simplify(num, times):\n",
    "    x = math.gcd(num, times)\n",
    "    return (num//x, times//x)\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        return get_24(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def judgePoint24(self, nums):\n",
    "        nums.sort()\n",
    "        a=[[1, 1, 1, 8], [1, 1, 2, 6], [1, 1, 2, 7], [1, 1, 2, 8], [1, 1, 2, 9], [1, 1, 3, 4], [1, 1, 3, 5], [1, 1, 3, 6], [1, 1, 3, 7], [1, 1, 3, 8], [1, 1, 3, 9], [1, 1, 4, 4], [1, 1, 4, 5], [1, 1, 4, 6], [1, 1, 4, 7], [1, 1, 4, 8], [1, 1, 4, 9], [1, 1, 5, 5], [1, 1, 5, 6], [1, 1, 5, 7], [1, 1, 5, 8], [1, 1, 6, 6], [1, 1, 6, 8], [1, 1, 6, 9], [1, 1, 8, 8], [1, 2, 2, 4], [1, 2, 2, 5], [1, 2, 2, 6], [1, 2, 2, 7], [1, 2, 2, 8], [1, 2, 2, 9], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 8], [1, 2, 3, 9], [1, 2, 4, 4], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4, 7], [1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5, 5], [1, 2, 5, 6], [1, 2, 5, 7], [1, 2, 5, 8], [1, 2, 5, 9], [1, 2, 6, 6], [1, 2, 6, 7], [1, 2, 6, 8], [1, 2, 6, 9], [1, 2, 7, 7], [1, 2, 7, 8], [1, 2, 7, 9], [1, 2, 8, 8], [1, 2, 8, 9], [1, 3, 3, 3], [1, 3, 3, 4], [1, 3, 3, 5], [1, 3, 3, 6], [1, 3, 3, 7], [1, 3, 3, 8], [1, 3, 3, 9], [1, 3, 4, 4], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4, 7], [1, 3, 4, 8], [1, 3, 4, 9], [1, 3, 5, 6], [1, 3, 5, 7], [1, 3, 5, 8], [1, 3, 5, 9], [1, 3, 6, 6], [1, 3, 6, 7], [1, 3, 6, 8], [1, 3, 6, 9], [1, 3, 7, 7], [1, 3, 7, 8], [1, 3, 7, 9], [1, 3, 8, 8], [1, 3, 8, 9], [1, 3, 9, 9], [1, 4, 4, 4], [1, 4, 4, 5], [1, 4, 4, 6], [1, 4, 4, 7], [1, 4, 4, 8], [1, 4, 4, 9], [1, 4, 5, 5], [1, 4, 5, 6], [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 5, 9], [1, 4, 6, 6], [1, 4, 6, 7], [1, 4, 6, 8], [1, 4, 6, 9], [1, 4, 7, 7], [1, 4, 7, 8], [1, 4, 7, 9], [1, 4, 8, 8], [1, 4, 8, 9], [1, 5, 5, 5], [1, 5, 5, 6], [1, 5, 5, 9], [1, 5, 6, 6], [1, 5, 6, 7], [1, 5, 6, 8], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 7, 9], [1, 5, 8, 8], [1, 5, 8, 9], [1, 5, 9, 9], [1, 6, 6, 6], [1, 6, 6, 8], [1, 6, 6, 9], [1, 6, 7, 9], [1, 6, 8, 8], [1, 6, 8, 9], [1, 6, 9, 9], [1, 7, 7, 9], [1, 7, 8, 8], [1, 7, 8, 9], [1, 7, 9, 9], [1, 8, 8, 8], [1, 8, 8, 9], [2, 2, 2, 3], [2, 2, 2, 4], [2, 2, 2, 5], [2, 2, 2, 7], [2, 2, 2, 8], [2, 2, 2, 9], [2, 2, 3, 3], [2, 2, 3, 4], [2, 2, 3, 5], [2, 2, 3, 6], [2, 2, 3, 7], [2, 2, 3, 8], [2, 2, 3, 9], [2, 2, 4, 4], [2, 2, 4, 5], [2, 2, 4, 6], [2, 2, 4, 7], [2, 2, 4, 8], [2, 2, 4, 9], [2, 2, 5, 5], [2, 2, 5, 6], [2, 2, 5, 7], [2, 2, 5, 8], [2, 2, 5, 9], [2, 2, 6, 6], [2, 2, 6, 7], [2, 2, 6, 8], [2, 2, 6, 9], [2, 2, 7, 7], [2, 2, 7, 8], [2, 2, 8, 8], [2, 2, 8, 9], [2, 3, 3, 3], [2, 3, 3, 5], [2, 3, 3, 6], [2, 3, 3, 7], [2, 3, 3, 8], [2, 3, 3, 9], [2, 3, 4, 4], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4, 7], [2, 3, 4, 8], [2, 3, 4, 9], [2, 3, 5, 5], [2, 3, 5, 6], [2, 3, 5, 7], [2, 3, 5, 8], [2, 3, 5, 9], [2, 3, 6, 6], [2, 3, 6, 7], [2, 3, 6, 8], [2, 3, 6, 9], [2, 3, 7, 7], [2, 3, 7, 8], [2, 3, 7, 9], [2, 3, 8, 8], [2, 3, 8, 9], [2, 3, 9, 9], [2, 4, 4, 4], [2, 4, 4, 5], [2, 4, 4, 6], [2, 4, 4, 7], [2, 4, 4, 8], [2, 4, 4, 9], [2, 4, 5, 5], [2, 4, 5, 6], [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 5, 9], [2, 4, 6, 6], [2, 4, 6, 7], [2, 4, 6, 8], [2, 4, 6, 9], [2, 4, 7, 7], [2, 4, 7, 8], [2, 4, 7, 9], [2, 4, 8, 8], [2, 4, 8, 9], [2, 4, 9, 9], [2, 5, 5, 7], [2, 5, 5, 8], [2, 5, 5, 9], [2, 5, 6, 6], [2, 5, 6, 7], [2, 5, 6, 8], [2, 5, 6, 9], [2, 5, 7, 7], [2, 5, 7, 8], [2, 5, 7, 9], [2, 5, 8, 8], [2, 5, 8, 9], [2, 6, 6, 6], [2, 6, 6, 7], [2, 6, 6, 8], [2, 6, 6, 9], [2, 6, 7, 8], [2, 6, 7, 9], [2, 6, 8, 8], [2, 6, 8, 9], [2, 6, 9, 9], [2, 7, 7, 8], [2, 7, 8, 8], [2, 7, 8, 9], [2, 8, 8, 8], [2, 8, 8, 9], [2, 8, 9, 9], [3, 3, 3, 3], [3, 3, 3, 4], [3, 3, 3, 5], [3, 3, 3, 6], [3, 3, 3, 7], [3, 3, 3, 8], [3, 3, 3, 9], [3, 3, 4, 4], [3, 3, 4, 5], [3, 3, 4, 6], [3, 3, 4, 7], [3, 3, 4, 8], [3, 3, 4, 9], [3, 3, 5, 5], [3, 3, 5, 6], [3, 3, 5, 7], [3, 3, 5, 9], [3, 3, 6, 6], [3, 3, 6, 7], [3, 3, 6, 8], [3, 3, 6, 9], [3, 3, 7, 7], [3, 3, 7, 8], [3, 3, 7, 9], [3, 3, 8, 8], [3, 3, 8, 9], [3, 3, 9, 9], [3, 4, 4, 4], [3, 4, 4, 5], [3, 4, 4, 6], [3, 4, 4, 7], [3, 4, 4, 8], [3, 4, 4, 9], [3, 4, 5, 5], [3, 4, 5, 6], [3, 4, 5, 7], [3, 4, 5, 8], [3, 4, 5, 9], [3, 4, 6, 6], [3, 4, 6, 8], [3, 4, 6, 9], [3, 4, 7, 7], [3, 4, 7, 8], [3, 4, 7, 9], [3, 4, 8, 9], [3, 4, 9, 9], [3, 5, 5, 6], [3, 5, 5, 7], [3, 5, 5, 8], [3, 5, 5, 9], [3, 5, 6, 6], [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9], [3, 5, 7, 8], [3, 5, 7, 9], [3, 5, 8, 8], [3, 5, 8, 9], [3, 5, 9, 9], [3, 6, 6, 6], [3, 6, 6, 7], [3, 6, 6, 8], [3, 6, 6, 9], [3, 6, 7, 7], [3, 6, 7, 8], [3, 6, 7, 9], [3, 6, 8, 8], [3, 6, 8, 9], [3, 6, 9, 9], [3, 7, 7, 7], [3, 7, 7, 8], [3, 7, 7, 9], [3, 7, 8, 8], [3, 7, 8, 9], [3, 7, 9, 9], [3, 8, 8, 8], [3, 8, 8, 9], [3, 8, 9, 9], [3, 9, 9, 9], [4, 4, 4, 4], [4, 4, 4, 5], [4, 4, 4, 6], [4, 4, 4, 7], [4, 4, 4, 8], [4, 4, 4, 9], [4, 4, 5, 5], [4, 4, 5, 6], [4, 4, 5, 7], [4, 4, 5, 8], [4, 4, 6, 8], [4, 4, 6, 9], [4, 4, 7, 7], [4, 4, 7, 8], [4, 4, 7, 9], [4, 4, 8, 8], [4, 4, 8, 9], [4, 5, 5, 5], [4, 5, 5, 6], [4, 5, 5, 7], [4, 5, 5, 8], [4, 5, 5, 9], [4, 5, 6, 6], [4, 5, 6, 7], [4, 5, 6, 8], [4, 5, 6, 9], [4, 5, 7, 7], [4, 5, 7, 8], [4, 5, 7, 9], [4, 5, 8, 8], [4, 5, 8, 9], [4, 5, 9, 9], [4, 6, 6, 6], [4, 6, 6, 7], [4, 6, 6, 8], [4, 6, 6, 9], [4, 6, 7, 7], [4, 6, 7, 8], [4, 6, 7, 9], [4, 6, 8, 8], [4, 6, 8, 9], [4, 6, 9, 9], [4, 7, 7, 7], [4, 7, 7, 8], [4, 7, 8, 8], [4, 7, 8, 9], [4, 7, 9, 9], [4, 8, 8, 8], [4, 8, 8, 9], [4, 8, 9, 9], [5, 5, 5, 5], [5, 5, 5, 6], [5, 5, 5, 9], [5, 5, 6, 6], [5, 5, 6, 7], [5, 5, 6, 8], [5, 5, 7, 7], [5, 5, 7, 8], [5, 5, 8, 8], [5, 5, 8, 9], [5, 5, 9, 9], [5, 6, 6, 6], [5, 6, 6, 7], [5, 6, 6, 8], [5, 6, 6, 9], [5, 6, 7, 7], [5, 6, 7, 8], [5, 6, 7, 9], [5, 6, 8, 8], [5, 6, 8, 9], [5, 6, 9, 9], [5, 7, 7, 9], [5, 7, 8, 8], [5, 7, 8, 9], [5, 8, 8, 8], [5, 8, 8, 9], [6, 6, 6, 6], [6, 6, 6, 8], [6, 6, 6, 9], [6, 6, 7, 9], [6, 6, 8, 8], [6, 6, 8, 9], [6, 7, 8, 9], [6, 7, 9, 9], [6, 8, 8, 8], [6, 8, 8, 9], [6, 8, 9, 9], [7, 8, 8, 9]]\n",
    "        if nums in a:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        ops = ['+','-1','-2','*','/1','/2']\n",
    "        cards = [(card, str(card)) for card in cards]\n",
    "        def dfs(cards):\n",
    "            n = len(cards)\n",
    "            if n == 1:\n",
    "                if (cards[0][0] - 24)**2 < 0.001:\n",
    "                    return cards[0][1]\n",
    "            for i in range(n):\n",
    "                for j in range(i+1,n):\n",
    "                    new_cards = [cards[k] for k in range(n) if k != i and k != j]\n",
    "                    for op in ops:\n",
    "                        new_card = None\n",
    "                        if op == '+':\n",
    "                            new_card = (cards[i][0] + cards[j][0], '('+cards[i][1]+'+'+cards[j][1]+')')\n",
    "                        elif op == '-1':\n",
    "                            new_card = (cards[i][0] - cards[j][0], '('+cards[i][1]+'-'+cards[j][1]+')')\n",
    "                        elif op == '-2':\n",
    "                            new_card = (cards[j][0] - cards[i][0], '('+cards[j][1]+'-'+cards[i][1]+')')\n",
    "                        elif op == '*':\n",
    "                            new_card = (cards[i][0] * cards[j][0], '('+cards[i][1]+'*'+cards[j][1]+')')\n",
    "                        elif op == '/1' and cards[j][0] != 0:\n",
    "                            new_card = (cards[i][0] / cards[j][0], '('+cards[i][1]+'/'+cards[j][1]+')')\n",
    "                        elif op == '/2' and cards[i][0] != 0:\n",
    "                            new_card = (cards[j][0] / cards[i][0], '('+cards[j][1]+'/'+cards[i][1]+')')\n",
    "                        if new_card:\n",
    "                            ans = dfs([new_card]+new_cards)\n",
    "                            if ans:\n",
    "                                return ans\n",
    "            return ''\n",
    "        ans = dfs(cards)\n",
    "        print(ans)\n",
    "        return len(ans)>0       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        target = 24\n",
    "        e = 1e-6\n",
    "        ADD, MUL, SUB, DIV = 0,1,2,3\n",
    "\n",
    "        def dfs(cards):\n",
    "            n = len(cards)\n",
    "            if n == 0:\n",
    "                return False\n",
    "            if n == 1:\n",
    "                return abs(cards[0]-target) < e\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i != j:\n",
    "                        tmp = []\n",
    "                        for k in range(n):\n",
    "                            if k != i and k != j:\n",
    "                                tmp.append(cards[k])\n",
    "                        x = cards[i]\n",
    "                        y = cards[j]\n",
    "                        for op in range(4):\n",
    "                            if op == ADD:\n",
    "                                res = x+y\n",
    "                            elif op == MUL:\n",
    "                                res = x*y\n",
    "                            elif op == SUB:\n",
    "                                res = x-y\n",
    "                            else:\n",
    "                                if abs(y) < e:\n",
    "                                    continue\n",
    "                                else:\n",
    "                                    res = x/y\n",
    "                            tmp.append(res)\n",
    "                            if dfs(tmp):\n",
    "                                return True\n",
    "                            tmp.pop()\n",
    "            return False\n",
    "\n",
    "        return dfs(cards)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def judgePoint24(self, c: List[int]) -> bool:\n",
    "        def fix(x):\n",
    "            if abs(x - 24)<=(1/(10**3)):\n",
    "                return 1 \n",
    "            return 0 \n",
    "        \n",
    "        def f(x):\n",
    "            a = x[0]\n",
    "            b = x[-1]\n",
    "            if b==0:\n",
    "                c1 = '1'\n",
    "            else:\n",
    "                c1 = a/b\n",
    "            c2 = a*b \n",
    "            c3 = a+b \n",
    "            c4 = a-b \n",
    "            return [c1, c2, c3, c4] \n",
    "        \n",
    "\n",
    "        def g(x):\n",
    "            if len(x)==2:\n",
    "                a = f(x)\n",
    "                b = f(x[::-1])\n",
    "                for j in a+b:\n",
    "                    if j!='1':\n",
    "                        if fix(j)==1:\n",
    "                            return 1 \n",
    "                return 0 \n",
    "            else:\n",
    "                s = SortedList(x)\n",
    "                for j in s:\n",
    "                    tmp = s[::]\n",
    "                    tmp.remove(j)\n",
    "                    for k in tmp:\n",
    "                        tmp1 = tmp[::]\n",
    "                        tmp1.remove(k)\n",
    "                        a = f((j, k)) \n",
    "                        for i in a:\n",
    "                            if i!='1':\n",
    "                                tmp2 = tmp1[::]\n",
    "                                tmp2.append(i)\n",
    "                                if g(list(tmp2)):\n",
    "                                    return 1 \n",
    "                            \n",
    "                return 0 \n",
    "      \n",
    "        return bool(g(c))\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from fractions import Fraction\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.can = False\n",
    "\n",
    "    def judgePoint24(self, cards: list) -> bool:\n",
    "        cp = list(cards)\n",
    "        self.dfs(cp)\n",
    "\n",
    "        return self.can\n",
    "\n",
    "    def dfs(self, cards):\n",
    "        if len(cards) == 1:\n",
    "            # print(cards[0])\n",
    "            if abs(cards[0] - 24.0) < 1e-6:\n",
    "                print(cards)\n",
    "                self.can = True\n",
    "            return\n",
    "\n",
    "        for i in range(len(cards)):\n",
    "            for j in range(i + 1, len(cards)):\n",
    "                x, y = Fraction(cards[i]), Fraction(cards[j])\n",
    "                cards.pop(j)\n",
    "                for op in ['+', '-', '*', '/']:\n",
    "                    for seq in [1, 0]:\n",
    "                        if op in ['+', '-', '*']:\n",
    "                            res = eval(str(x) + op + str(y)) if seq else eval(str(y) + op + str(x))\n",
    "                        else:\n",
    "                            if seq:\n",
    "                                if y == 0:\n",
    "                                    continue\n",
    "                                res = Fraction(x, y)\n",
    "                            else:\n",
    "                                if x == 0:\n",
    "                                    continue\n",
    "                                res = Fraction(y,x)\n",
    "\n",
    "                        cards[i] = res\n",
    "                        self.dfs(cards)\n",
    "                cards[i] = x\n",
    "                cards.insert(j, y)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def czh(self,i,result,path,cards,booll):\n",
    "        a={0:[0,4],1:[0,6],2:[2,6],3:[2,8],4:[4,8]}\n",
    "        b={0:\"+\",1:\"-\",2:\"*\",3:\"/\"}\n",
    "        if booll:\n",
    "            return\n",
    "        if i==4:\n",
    "            for kk in range(0,5):\n",
    "                s=path[:]\n",
    "                s.insert(a[kk][0],\"(\")\n",
    "                s.insert(a[kk][1],\")\")\n",
    "                ss = ''.join([str(num) for num in s])\n",
    "                try:\n",
    "                    rr=eval(ss)\n",
    "                except:\n",
    "                    aaa=1\n",
    "                \n",
    "                if abs(rr-24)<0.001:\n",
    "                    result.append(s[:])\n",
    "                    booll=True\n",
    "            s = path[:]\n",
    "            s.insert(0, \"(\")\n",
    "            s.insert(4, \")\")\n",
    "            s.insert(6, \"(\")\n",
    "            s.insert(10, \")\")\n",
    "            ss = ''.join([str(num) for num in s])\n",
    "            try:\n",
    "                rr = eval(ss)\n",
    "            except:\n",
    "                aaa = 1\n",
    "            if abs(rr - 24) < 0.001:\n",
    "                result.append(s[:])\n",
    "\n",
    "            return\n",
    "        for kk in range (0,4):\n",
    "            path.append(b[kk])\n",
    "            path.append(cards[i])\n",
    "            self.czh(i+1,result,path,cards,booll)\n",
    "            path.pop()\n",
    "            path.pop()\n",
    "        return\n",
    "    def simba(self,i,cards,pathh,rresult):\n",
    "        if i==4:\n",
    "            p=[]\n",
    "            for kkk in pathh:\n",
    "                p.append(cards[kkk])\n",
    "            rresult.append(p)\n",
    "            return\n",
    "        for j in range (0,4):\n",
    "            if not(j in pathh):\n",
    "                pathh.append(j)\n",
    "                self.simba(i+1,cards,pathh,rresult)\n",
    "                pathh.pop() \n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "       result=[]\n",
    "\n",
    "       rresult=[]\n",
    "       self.simba(0,cards,[],rresult)\n",
    "       for i in rresult:\n",
    "           path=[]\n",
    "           path.append(i[0])\n",
    "           self.czh(1,result,path,i,False)\n",
    "           if len(result)>0:\n",
    "               break\n",
    "       if len(result)>0:\n",
    "           return(True)\n",
    "       else:\n",
    "           return(False)\n",
    "        \n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        @lru_cache\n",
    "        def help(s):\n",
    "            if len(s) == 1:\n",
    "                return {int(s)}\n",
    "            res = set()\n",
    "            for i in range(1, len(s)):\n",
    "                res |= {a + b for a in help(s[:i]) for b in help(s[i:])}\n",
    "                res |= {a - b for a in help(s[:i]) for b in help(s[i:])}\n",
    "                res |= {a * b for a in help(s[:i]) for b in help(s[i:])}\n",
    "                res |= {a / b for a in help(s[:i]) for b in help(s[i:]) if b}\n",
    "            return res\n",
    "        \n",
    "        for perm in permutations(cards):\n",
    "            s = \"\".join(str(x) for x in perm)\n",
    "            results = {round(x) for x in help(s) if abs(x - round(x)) < 1e-10}\n",
    "            if 24 in results: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def get_permutations(nums):\n",
    "            nums.sort()\n",
    "            permutations = []\n",
    "            tmp = []\n",
    "            visited = [False] * len(nums)\n",
    "            backtracking(nums, tmp, visited, permutations)\n",
    "            return permutations\n",
    "\n",
    "        def backtracking(nums, tmp, visited, permutations):\n",
    "            if len(nums) == len(tmp):\n",
    "                permutations.append(tmp.copy())\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:\n",
    "                    continue\n",
    "                elif not visited[i]:\n",
    "                    visited[i] = True\n",
    "                    backtracking(nums, tmp + [nums[i]], visited, permutations)\n",
    "                    visited[i] = False\n",
    "        def caculate(perm: List[int]) -> bool:\n",
    "            if len(perm) == 1:\n",
    "                return abs(perm[0] - 24) <= 10 ** (-10)\n",
    "            \n",
    "            for i in range(len(perm)-1):\n",
    "                tmp = []\n",
    "                tmp.append(perm[i]+perm[i+1])\n",
    "                tmp.append(perm[i]-perm[i+1])\n",
    "                tmp.append(perm[i+1]-perm[i])\n",
    "                tmp.append(perm[i]*perm[i+1])\n",
    "                if perm[i+1] != 0:\n",
    "                    tmp.append(perm[i]/perm[i+1])\n",
    "                if perm[i] != 0:\n",
    "                    tmp.append(perm[i+1]/perm[i])\n",
    "                for t in tmp:\n",
    "                    new_perm = perm.copy()\n",
    "                    new_perm[i] = t\n",
    "                    new_perm.pop(i+1)\n",
    "                    if caculate(new_perm):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        \n",
    "        permutations = get_permutations(cards)\n",
    "        for perm in permutations:\n",
    "            if caculate(perm):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, nums: List[int]) -> bool:\n",
    "        queue = deque([nums])\n",
    "        EPS = 0.0001\n",
    "        \n",
    "        seen = set()\n",
    "        \n",
    "        while queue:\n",
    "            current_state = queue.popleft()\n",
    "\n",
    "            if len(current_state) == 1 and abs(current_state[0] - 24.0) <= EPS:\n",
    "                return True\n",
    "            \n",
    "            seen.add(tuple(current_state))\n",
    "            for i in range(len(current_state)):\n",
    "                without_i = current_state[:i] + current_state[i+1:]\n",
    "                for j in range(len(without_i)):\n",
    "                    x, y = current_state[i], without_i[j]\n",
    "                    \n",
    "                    next_state = without_i[:j] + without_i[j+1:]\n",
    "                    next_values = [x + y, x - y, y - x, x * y]\n",
    "                    \n",
    "                    if y != 0:\n",
    "                        next_values.append(x / y)\n",
    "                    \n",
    "                    if x != 0:\n",
    "                        next_values.append(y / x)\n",
    "                    \n",
    "                    for val in next_values:\n",
    "                        if tuple(next_state + [val]) not in seen:\n",
    "                            queue.append(next_state + [val])\n",
    "                            seen.add(tuple(next_state + [val]))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        nodes = [Node(card) for card in cards]\n",
    "\n",
    "        def calculation(array):\n",
    "            if len(array) == 1:\n",
    "                return array\n",
    "            \n",
    "            ans = []\n",
    "            for i in range(1, len(array)):\n",
    "                for first in calculation(array[:i]):\n",
    "                    for second in calculation(array[i:]):\n",
    "                        # print(first, second)\n",
    "                        ans.extend(first.operations(second))\n",
    "            if len(array) == 4:\n",
    "                for middle in calculation(array[1:3]):\n",
    "                    ans.extend(calculation([array[0], middle, array[-1]]))\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        array = self.getPermuation(nodes)\n",
    "        for lst in array:\n",
    "            values = calculation(lst)\n",
    "            for node in values:\n",
    "                if node.getValue() == 24:\n",
    "                    return True\n",
    "\n",
    "        return False\n",
    "    \n",
    "    def getPermuation(self, array):\n",
    "        if len(array) == 1:\n",
    "            return [array]\n",
    "        ans = []\n",
    "        for i in range(len(array)):\n",
    "            ans.extend([[array[i]] + lst for lst in self.getPermuation(array[:i] + array[i+1:])])\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, numerator, denominator=1):\n",
    "        self.numerator = numerator\n",
    "        self.denominator = denominator\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"<{self.numerator}, {self.denominator}>\"\n",
    "\n",
    "    def times(self, other):\n",
    "        return Node(self.numerator * other.numerator, self.denominator * other.denominator)\n",
    "\n",
    "    def devide(self, other):\n",
    "        return Node(self.numerator * other.denominator, self.denominator * other.numerator)\n",
    "\n",
    "    def plus(self, other):\n",
    "        return Node(self.numerator * other.denominator + self.denominator * other.numerator, self.denominator * other.denominator)\n",
    "\n",
    "    def minus(self, other):\n",
    "        return Node(self.numerator * other.denominator - self.denominator * other.numerator, self.denominator * other.denominator)\n",
    "    \n",
    "    def operations(self, other):\n",
    "        return [self.times(other), self.devide(other), self.plus(other), self.minus(other)] \n",
    "    \n",
    "    def getValue(self):\n",
    "        if self.denominator == 0:\n",
    "            return float(\"inf\")\n",
    "        return self.numerator / self.denominator\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        s0=['+','-','*','/']\n",
    "        ################################   l0=[8,4,2,3] (8-4)*(2+3)=24\n",
    "        l0=cards\n",
    "        def 排列(ls,counter):\n",
    "            ls1=[]\n",
    "            ls0=ls.copy()\n",
    "            while counter!=0+1:\n",
    "                for i in ls:\n",
    "                    for j in ls0:\n",
    "                        ls1.append(i+j)\n",
    "                ls=ls1.copy()\n",
    "                ls1=[]\n",
    "                counter-=1\n",
    "            return ls\n",
    "        def 不重复的排列(ls0,counter):\n",
    "            ls=ls0.copy()\n",
    "            ls1=[]\n",
    "            while counter!=0+1:\n",
    "                for i in ls:\n",
    "                    for j in ls0:\n",
    "                        if j in i:\n",
    "                            continue\n",
    "                        ls1.append(i+j)\n",
    "                ls=ls1.copy()\n",
    "                ls1=[]\n",
    "                counter-=1\n",
    "            return ls\n",
    "        s=排列(s0.copy(),3)\n",
    "        l1=不重复的排列(list(map(str,list(range(4)))).copy(),2)\n",
    "        l2=不重复的排列(list(map(str,list(range(3)))).copy(),2)\n",
    "        l3=不重复的排列(list(map(str,list(range(2)))).copy(),2)\n",
    "        l=[]\n",
    "        for i in l1:\n",
    "            for j in l2:\n",
    "                for k in l3:\n",
    "                    l.append(i+j+k)          #先确定好操作的顺序的组合的序号\n",
    "        ans=[]\n",
    "        for i in s:\n",
    "            for j in l:\n",
    "                ll=l0.copy()\n",
    "                for k in range(3):\n",
    "                    jump=False\n",
    "                    if int(j[2*k])>int(j[2*k+1]):                        #不能直接写a0,a1=ll.pop(int(j[2*k])),ll.pop(int(j[2*k+1]))\n",
    "                        a0,a1=ll.pop(int(j[2*k])),ll.pop(int(j[2*k+1]))  #要考虑pop后的序号问题\n",
    "                    else:                                                #也不能简单粗暴写为a0,a1=ll.pop(int(j[2*k])),ll.pop(int(j[2*k+1])-1)\n",
    "                        a1,a0=ll.pop(int(j[2*k+1])),ll.pop(int(j[2*k]))  #要先比较序号大小，若位置在后面则要减1，否则就不用减1\n",
    "                    if a1==0 and i[k]=='/':\n",
    "                        jump=True                                        #防止除以0\n",
    "                        break\n",
    "                    ll.append(eval(str(a0)+i[k]+str(a1)))\n",
    "                if jump==True:                                           #配合前面，要跳过-0.00001<(ll[0]-24)<+0.0001:\n",
    "                    continue\n",
    "                if -0.00001<(ll[0]-24)<+0.0001:\n",
    "                    return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
